#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: search.py
@time: 2021/12/18 13:44
@desc:
'''
# 折半查找: 从有序数组中查找
def binary_search(nums: list, x):
    low, high = 0, len(nums)-1
    mid = (low+high)//2
    while low<=high:
        if nums[mid]==x:
            return mid
        elif x<nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
        mid = (low+high)//2
    return -1



if __name__ == '__main__':
    list = [1,3, 4, 5, 6,7,9,20, 29]
    x = 20
    res = binary_search(list, x)
    print(res)